Задача #M025D

Память 16 MB Время 1000 ms Сложность 25 %

Sayr

Sakrashni yaxshi ko’radigan quyoncha bir kun \(N \times M\) jadvalning ichiga tushib qoldi. U jadvalning \((1,1)\) katagida turbid va u \((N, M)\) katakka bormoqchi. Jadvalning har bir katagi yoki oddiy yer yoki tikanakzor bo’lishi mumkin. Quyoncha bir sakrashni o’zi turgan joydan pastdagi yoki o’ngdagi eng yaqin yerga sakrashi mumkin(ya’ni tikanakzorlarni sakrab ham o’tsa bo’ladi). Quyonchani \((1,1)\) katakdan \((N,M)\) katakka yetib borish ketma-ketligining variantlar sonini toping.

Входные данные:

Kirish faylining dastlabki satrida ikkita butun son, \(N\) va \(M (1 \le N, M \le 1000)\) sonlari kiritiladi. Keyingi qatordan boshlab \(N\) ta qatorda \(M\) tadan raqam (0 – yer, 1 – tikanakzor) kiritiladi.

Выходные данные:

Chiqish faylida yagona butun son, so’ralgan javobni \(10^9+7\) ga bo’lgandagi qoldig’ini chop eting.

Примеры

#	input.txt	output.txt
1	3 3 000 011 000	3

Примечание:

(1,1)=>(2,1)=>(3,1)=>(3,2)=>(3,3)

(1,1)=>(1,2)=>(3,2)=>(3,3)

(1,1)=>(1,2)=>(1,3)=>(3,3)

Telegram Facebook

Отправить решение

Пожалуйста, войдите в систему, чтобы выполнить это действие,если у вас нет учетной записи, вы можете зарегистрироваться в любое время